package com.base.leetcode;

/**
 * @Author: hdhao
 * @Create: 2023/3/30 - 20:18
 * @Version: v1.0
 */
//合并两个有序链表
public class Leetcode21 {
    public static void main(String[] args) {

    }
    //合并两个有序链表为一个新的有序链表
    public static ListNode mergeTwoLists(ListNode p1,ListNode p2){
        //新链表的哨兵节点
        ListNode s = new ListNode(-1,null);
        //新链表指针变量
        ListNode p = s;
        //当p1和p2 有一个为null时，退出循环，将两一个链表剩下的节点全部链接到新链表
        while (p1!=null && p2!=null){
            //将p1 和 p2 中较小的值链接到新链表后边
            if (p1.val < p2.val){
                p.next = p1;
                p1 = p1.next;
            }else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1!=null){
            p.next = p1;
        }
        if (p2 !=null){
            p.next = p2;
        }
        return s.next;
    }
    //递归实现
    public static ListNode mergeTwoLists2(ListNode p1,ListNode p2){
        if (p2 == null){
            return p1;
        }
        if (p1 == null){
            return p2;
        }
        if (p1.val < p2.val){
            p1.next = mergeTwoLists2(p1.next,p2);
            return p1;
        }else {
            p2.next = mergeTwoLists2(p1,p2.next);
            return p2;
        }
    }
}
